package a.codetop.归并;

import 其他.DataStructure.ListNode;


public class 归并_合有序链表 {
    public ListNode sortList(ListNode head) {
        if(head==null)return null;
        ListNode tail = head;
        while(tail.next!=null){
            tail = tail.next;
        }
        //开始
        return merge_sort_link(head, tail);
    }

    //归并维护2个head,2个参数同时维护
    private ListNode merge_sort_link(ListNode h1, ListNode h2) {
        if(h1==h2)return h1;

        //找中点
        ListNode mid = findMidNode(h1, h2);

        ListNode nh1 = merge_sort_link(h1, mid);
        ListNode tmpMidNext = mid.next; mid.next = null; //切
        ListNode nh2 =merge_sort_link(tmpMidNext, h2);

        // 后序
        return merge2OrderLink(nh1,nh2); // 返回 合一 的 左head
    }

    //合有序链表
    private ListNode merge2OrderLink(ListNode h1, ListNode h2) {
        ListNode dm = new ListNode(-1);
        ListNode dmt = dm;

        while(h1!=null && h2!=null){ // 不是h1.next
            if(h1.val<=h2.val){
                dm.next = h1;dm = dm.next;h1 = h1.next;
            }else {
                dm.next = h2;dm = dm.next;h2 = h2.next;
            }
        }

        if(h1 == null)dm.next = h2;
        if(h2 == null)dm.next = h1;
        return dmt.next;
    }

    //有右边界的找中点
    private ListNode findMidNode(ListNode h, ListNode t) {
        ListNode s=h,f=h.next;
        while (f!=t.next && f.next!=t.next) { //null改t.next
            s = s.next;
            f = f.next.next;
        }
        return s;
    }
}
